11338. Кузнечик и цепь

Однажды кузнечик, как обычно, гулял по лугу. Он наткнулся на цепь. Его интересовал один вопрос какой минимальный навык прыжка ему нужен, чтобы дойти до конца цепи. Обратите внимание, что цепочка состоит только из заглавных английских букв, и кузнечик может прыгать только на гласные буквы в цепочке.

Сначала кузнечик стоит слева от крайнего левого символа в цепочке, и его цель попасть в ячейку прямо справа от самого правого символа. За один прыжок кузнечик может прыгнуть на любое расстояние от 1 до своего навыка прыжка. Давайте посмотрим на картинку ниже для ясности.

Гласные буквы это A, E, I, O, U и Y.

Вход. Одна строка S (1 ≤ |S| ≤ 100), состоящая из заглавных английских букв.

Выход. Выведите одно число – минимальную прыгучесть кузнечика.

Пример входа 1	Пример выхода 1
ABABBBACFEYUKOTT	4
Пример входа 2	Пример выхода 2
AAA	1

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Пусть строка S начинается с позиции 0. Тогда изначально кузнечик находится в позиции с координатой pos = -1. Для минимизации прыгучести кузнечику выгодно прыгать на все гласные буквы подряд. И в конце совершить прыжок на позицию, следующую за последней буквой.

Перебираем буквы, поддерживаем текущее положение кузнечика pos. Если в позиции i расположена гласная буква, то совершаем туда прыжок длиной i – pos. После каждого прыжка изменяем положение кузнечика pos = i.

Ответом будет максимум из длин всех прыжков.

Реализация алгоритма

Читаем входную строку.

cin >> s;

Изначально кузнечик расположен в позиции pos = -1.

pos = -1;

Минимальную прыгучесть кузнечика вычисляем в переменной res.

res = 0;

Перебираем буквы входной строки.

for (i = 0; i < s.size(); i++)

Если в позиции i расположена гласная буква, то совершаем туда прыжок. Длина прыжка равна i – pos. Следующий прыжок уже будет совершаться с позиции i, поэтому положим pos = i.

if (s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' ||

s[i] == 'U' || s[i] == 'Y')

{

res = max(res, i - pos);

pos = i;

}

Совершаем последний прыжок: из последней гласной буквы в позицию s.size() (позиция за последней буквой).

res = max(res, (int)s.size() - pos);

Выводим ответ.

cout << res << endl;

Python реализация

Читаем входную строку.

s = input()

Изначально кузнечик расположен в позиции pos = -1.

pos = -1

Минимальную прыгучесть кузнечика вычисляем в переменной res.

res = 0

Перебираем буквы входной строки.

for i in range(len(s)):

Если в позиции i расположена гласная буква, то совершаем туда прыжок. Длина прыжка равна i – pos. Следующий прыжок уже будет совершаться с позиции i, поэтому положим pos = i.

if s[i] in ['A', 'E', 'I', 'O', 'U', 'Y']:

res = max(res, i - pos)

pos = i

Совершаем последний прыжок: из последней гласной буквы в позицию len(s) (позиция за последней буквой).

res = max(res, len(s) - pos)

Выводим ответ.

print(res)